package com.guang.guiji.sort;

import java.util.Random;

public class InsertSort {
	// 插入排序
	public static void insertSort(int a[]) {
		int temp = 0;
		for (int i = 1; i < a.length; i++) {
			for (int j = i; j > 0 && a[j - 1] > a[j]; j--) {
				temp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = temp;
			}
		}

	}

	// 改进的插入排序
	public static void betterInsertSort(int a[]) {
		int temp = 0;
		for (int i = 1; i < a.length; i++) {
			int j = 0;
			temp = a[i];
			/* 改进的部分 */
			for (j = i; j > 0 && a[j - 1] > temp; j--) {
				a[j] = a[j - 1];
			}
			a[j] = temp;
			/* 到这止 */
		}

	}

	// 冒泡排序
	public static void bubbleSort(int a[]) {
		int temp = 0;
		int tag = 0;// 标志位,判断是否退出循环
		for (int i = 0; i < a.length; i++) {
			tag = 0;
			
			for (int j = 0; j < a.length - i - 1; j++) {
				if (a[j] > a[j + 1]) {
					temp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = temp;
					tag = 1;
				}
			}

			if (tag == 0) {
				break;
			}
		}

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		long startTime = System.currentTimeMillis();// 返回以毫秒为单位的当前时间，即程序开始时间
		int[] a = new int[100000];
		Random random = new Random();
		for (int i = 0; i < a.length; i++) {
			a[i] = random.nextInt(10);
		}

		InsertSort.insertSort(a);//插入排序
		//InsertSort.betterInsertSort(a);// 改进的插入排序
		//InsertSort.bubbleSort(a);

		for (int i = 0; i < a.length; i++) {
			System.out.println(a[i]);
		}

		long entTime = System.currentTimeMillis();// 返回以毫秒为单位的当前时间，即程序结束时间
		System.out.println((entTime - startTime) + "ms");// 打印程序运行时间
	}

}
